﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MyOnlineScheduling
{
    static class SchedulingAlgorithms
    {
        // bez wywłaszczania
        public static void ShortestWeightedProcessingTime(Processor[] processors, Task[] tasks)
        {
            int m = processors.Length;
            int n = tasks.Length;

            bool notFinished = true;

            TaskHeap taskHeap = new TaskHeap();
            ProcessorDualHeap processorHeap = new ProcessorDualHeap(m);

            int possibleCurrentTime;
            int currentTime = tasks[0].arrivalTime;
            int i = 0;
            int endTime;

            int maxHeapIndex;

            PartTask newTask;

            while (notFinished)
            {
                while (i < n && tasks[i].arrivalTime == currentTime)
                {
                    taskHeap.insert(new PartTask(tasks, i));
                    i++;
                }

                endTime = processors[processorHeap.indexOfMin()].endTime;

                while (taskHeap.Count() > 0 && endTime <= currentTime)
                {
                    newTask = taskHeap.heapExtractMin();
                    processors[processorHeap.indexOfMin()].scheduleTaskOnProcessor(newTask,currentTime);

                    maxHeapIndex = processorHeap.getMaxHeapIndex(0);
                    processorHeap.minHeapify(processors, 0);
                    //processorHeap.maxHeapify(processors, maxHeapIndex, currentTime);

                    endTime = processors[processorHeap.indexOfMin()].endTime;
                }

                if (i == n && taskHeap.Count() == 0)
                    notFinished = false;

                /*oldCurrentTime = currentTime;

                if (i < n)
                {
                    if (oldCurrentTime == currentTime && taskHeap.Count() == 0)
                        currentTime = Math.Max(processors[processorHeap.indexOfMin()].endTime, tasks[i].arrivalTime);
                    else
                        currentTime = Math.Min(processors[processorHeap.indexOfMin()].endTime, tasks[i].arrivalTime);
                }
                else
                    currentTime = processors[processorHeap.indexOfMin()].endTime;*/

                //currentTime++;

                if (i < n)
                {
                    possibleCurrentTime = Math.Min(processors[processorHeap.indexOfMin()].endTime, tasks[i].arrivalTime);
                }
                else
                    possibleCurrentTime = processors[processorHeap.indexOfMin()].endTime;

                currentTime = Math.Max(possibleCurrentTime, currentTime + 1);
            }
        }

        public static void RandomWithSlightImprovement(Processor[] processors, Task[] tasks)
        {
            int m = processors.Length;
            int n = tasks.Length;

            const int kMax = 3;
            int k;

            int chosenTaskIndex;
            int tempIndex;

            double minWeigthedTime;
            double weightedTime;

            int currentTime = tasks[0].arrivalTime;
            int possibleCurrentTime;

            int endTime;

            bool notFinished = true;

            ProcessorDualHeap processorHeap = new ProcessorDualHeap(m);
            List<PartTask> pendingTasks = new List<PartTask>();
            List<PartTask> currentTasks = new List<PartTask>();

            int i = 0;
            int firstAvailableProcessorIndex;

            while (notFinished)
            {
                while (i < n && tasks[i].arrivalTime == currentTime)
                {
                    pendingTasks.Add(new PartTask(tasks,i));
                    i++;
                }

                endTime = processors[processorHeap.indexOfMin()].endTime;

                while (pendingTasks.Count > 0 && endTime <= currentTime)
                {
                    k = kMax;
                    if (pendingTasks.Count > kMax)
                    {
                        tempIndex = InstanceGenerator.randomNumber(0, pendingTasks.Count - 1);
                        currentTasks.Add(pendingTasks.ElementAt(tempIndex));
                        pendingTasks.RemoveAt(tempIndex);

                        tempIndex = InstanceGenerator.randomNumber(0, pendingTasks.Count - 1);
                        currentTasks.Add(pendingTasks.ElementAt(tempIndex));
                        pendingTasks.RemoveAt(tempIndex);

                        tempIndex = InstanceGenerator.randomNumber(0, pendingTasks.Count - 1);
                        currentTasks.Add(pendingTasks.ElementAt(tempIndex));
                        pendingTasks.RemoveAt(tempIndex);
                    }
                    else
                    {
                        k = pendingTasks.Count;

                        for (int j = 0; j < k; j++)
                        {
                            currentTasks.Add(pendingTasks.ElementAt(0));
                            pendingTasks.RemoveAt(0);
                        }
                    }

                    minWeigthedTime = (double)tasks[currentTasks[0].taskId].duration / tasks[currentTasks[0].taskId].weight;
                    chosenTaskIndex = 0;

                    for (int j = 1; j < k; j++)
                    {
                        weightedTime = (double)tasks[currentTasks[j].taskId].duration / tasks[currentTasks[j].taskId].weight;
                        if (weightedTime < minWeigthedTime)
                        {
                            minWeigthedTime = weightedTime;
                            chosenTaskIndex = j;
                        }
                    }
                    
                    firstAvailableProcessorIndex = processorHeap.indexOfMin();
                    processors[firstAvailableProcessorIndex].scheduleTaskOnProcessor(currentTasks[chosenTaskIndex],currentTime);
                    currentTasks.RemoveAt(chosenTaskIndex);
                    processorHeap.minHeapify(processors, 0);

                    for (int j = 0; j < currentTasks.Count; j++)
                    {
                        pendingTasks.Add(currentTasks[j]);
                    }
                    currentTasks.Clear();

                    endTime = processors[processorHeap.indexOfMin()].endTime;
                }

                if (i == n && pendingTasks.Count == 0)
                    notFinished = false;

                /*oldCurrentTime = currentTime;

                if (i < n)
                {
                    if (oldCurrentTime == currentTime && pendingTasks.Count == 0)
                        currentTime = Math.Max(processors[processorHeap.indexOfMin()].endTime, tasks[i].arrivalTime);
                    else
                        currentTime = Math.Min(processors[processorHeap.indexOfMin()].endTime, tasks[i].arrivalTime);
                }
                else
                    currentTime = processors[processorHeap.indexOfMin()].endTime;*/

                if (i < n)
                {
                    possibleCurrentTime = Math.Min(processors[processorHeap.indexOfMin()].endTime, tasks[i].arrivalTime);
                }
                else
                    possibleCurrentTime = processors[processorHeap.indexOfMin()].endTime;

                currentTime = Math.Max(possibleCurrentTime, currentTime + 1);

                //currentTime++;
            }
        }

        // z wywłaszczaniem
        public static void PseudoShortestWeightedTimeRemainingFirst(Processor[] processors, Task[] tasks)
        {
            int m = processors.Length;
            int n = tasks.Length;

            bool notFinished = true;

            TaskHeap taskHeap = new TaskHeap();
            ProcessorDualHeap processorHeap = new ProcessorDualHeap(m);

            int possibleCurrentTime;
            int currentTime = tasks[0].arrivalTime;
            int i = 0;
            int endTime, taskArrivalTime;//, lastTaskArrivalTime;

            int maxHeapIndex, minHeapIndex;

            PartTask newTask, tempTask;

            while (notFinished)
            {
                while (i < n && tasks[i].arrivalTime == currentTime)
                {
                    taskHeap.insert(new PartTask(tasks, i));
                    i++;
                }

                endTime = processors[processorHeap.indexOfMax()].endTime;
                //int lastIndex = processors[processorHeap.indexOfMax()].taskList.Count - 1;

                //lastTaskArrivalTime = processors[processorHeap.indexOfMax()].taskList[lastIndex].arrivalTime;

                while (taskHeap.Count() > 0 && endTime > currentTime)// && lastTaskArrivalTime < currentTime)
                {
                    endTime = processors[processorHeap.indexOfMax()].endTime;

                    newTask = taskHeap.heapExtractMin();
                    tempTask = processors[processorHeap.indexOfMax()].expropriateTaskWithCheck(newTask, currentTime);

                    if (tempTask != null)
                    {
                        processors[processorHeap.indexOfMax()].scheduleTaskOnProcessor(newTask, currentTime);

                        minHeapIndex = processorHeap.getMinHeapIndex(0);
                        processorHeap.maxHeapify(processors, 0, currentTime);
                        if (processorHeap.minHeapify(processors, minHeapIndex) == false)
                            processorHeap.minHeapUp(processors, minHeapIndex);

                        taskHeap.insert(tempTask);
                    }
                    else
                    {
                        taskHeap.insert(newTask);
                        break;
                    }

                    endTime = processors[processorHeap.indexOfMin()].endTime;
                    //lastIndex = processors[processorHeap.indexOfMax()].taskList.Count - 1;
                    //arrivalTime = processors[processorHeap.indexOfMax()].taskList[lastIndex].arrivalTime;
                }

                endTime = processors[processorHeap.indexOfMin()].endTime;
                if (taskHeap.Count() > 0) taskArrivalTime = taskHeap.heapGetMin().arrivalTime;
                else taskArrivalTime = -1;

                while (taskHeap.Count() > 0 && (endTime == currentTime || (endTime <= currentTime && taskArrivalTime == currentTime)))
                {
                    newTask = taskHeap.heapExtractMin();
                    processors[processorHeap.indexOfMin()].scheduleTaskOnProcessor(newTask, currentTime);

                    maxHeapIndex = processorHeap.getMaxHeapIndex(0);
                    processorHeap.minHeapify(processors, 0);

                    if (processorHeap.maxHeapify(processors, maxHeapIndex, currentTime) == false)
                        processorHeap.maxHeapUp(processors, maxHeapIndex, currentTime);

                    endTime = processors[processorHeap.indexOfMin()].endTime;
                }

                if (i == n && taskHeap.Count() == 0)
                    notFinished = false;

                if (i < n)
                {
                        possibleCurrentTime = Math.Min(processors[processorHeap.indexOfMin()].endTime, tasks[i].arrivalTime);
                }
                else
                    possibleCurrentTime = processors[processorHeap.indexOfMin()].endTime;

                currentTime = Math.Max(possibleCurrentTime, currentTime + 1);
            }
        }

        public static void ShortestWeightedTimeRemainingFirst(Processor[] processors, Task[] tasks)
        {
            int m = processors.Length;
            int n = tasks.Length;

            bool notFinished = true;

            TaskHeap taskHeap = new TaskHeap();
            ProcessorDualHeap processorHeap = new ProcessorDualHeap(m);

            int possibleCurrentTime;
            int currentTime = tasks[0].arrivalTime;
            int i = 0;
            int endTime, taskArrivalTime;

            PartTask newTask, tempTask;

            while (notFinished)
            {
                while (i < n && tasks[i].arrivalTime == currentTime)
                {
                    taskHeap.insert(new PartTask(tasks, i));
                    i++;
                }

                for (int j = 0; j < m; j++)
                {
                    if (taskHeap.Count() > 0 && processors[j].endTime > currentTime)
                    {
                        tempTask = processors[j].expropriateTask(currentTime);

                        if (tempTask != null)
                        {
                            if (processorHeap.minHeapify(processors, processorHeap.getMinHeapIndexFromRealIndex(j)) == false)
                                processorHeap.minHeapUp(processors, processorHeap.getMinHeapIndexFromRealIndex(j));

                            taskHeap.insert(tempTask);
                        }
                        else
                            Console.Write("oj");
                    }
                }

                endTime = processors[processorHeap.indexOfMin()].endTime;
                if (taskHeap.Count() > 0) taskArrivalTime = taskHeap.heapGetMin().arrivalTime;
                else taskArrivalTime = -1;

                while (taskHeap.Count() > 0 && (endTime == currentTime || (endTime <= currentTime && taskArrivalTime == currentTime)))
                {
                    newTask = taskHeap.heapExtractMin();
                    processors[processorHeap.indexOfMin()].scheduleTaskOnProcessor(newTask, currentTime);

                    processorHeap.minHeapify(processors, 0);
                    endTime = processors[processorHeap.indexOfMin()].endTime;
                }

                if (i == n && taskHeap.Count() == 0)
                    notFinished = false;

                if (i < n)
                {
                    possibleCurrentTime = Math.Min(processors[processorHeap.indexOfMin()].endTime, tasks[i].arrivalTime);
                }
                else
                    possibleCurrentTime = processors[processorHeap.indexOfMin()].endTime;

                currentTime = Math.Max(possibleCurrentTime, currentTime + 1);
            }
        }

        public static void AverageLength()
        { }
    }
}
